package com.leetcode.test.linklist.classic;

import com.leetcode.test.linklist.ListNode;
import org.junit.Assert;
import org.junit.Test;

/**
 * 反转链表
 * <p>
 * 问题：https://leetcode-cn.com/explore/learn/card/linked-list/195/classic-problems/750/ <br><br>
 * 官方解答：https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode/
 */
public class 反转链表 {

    @Test
    public void reverse() {
//        输入: 1->2->3->4->5->NULL
//        输出: 5->4->3->2->1->NULL
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        ListNode head = node1;

        // 反转
        reverse(head);

        Assert.assertEquals(node5.next, node4);
        Assert.assertEquals(node4.next, node3);
        Assert.assertEquals(node3.next, node2);
        Assert.assertEquals(node2.next, node1);
        Assert.assertEquals(node1.next, null);
    }

    /**
     * 反转链表
     *
     * @return 返回新的头部
     */
    private ListNode reverse(ListNode head) {
        if (head == null) {
            return null;
        } else if (head.next == null) {
            return head;
        }

        // 指针始终停留在初始头节点，因为后面的节点会不断移动
        ListNode curr = head;

        while (curr.next != null) {
            ListNode temp = curr.next;
            curr.next = curr.next.next;
            temp.next = head;
            head = temp;
        }

        return head;
    }

}
